import util.TreeNode;

/**
 * Created by losor on 2017/3/9.
 */
public class _437_PathSumIII {
    //重要
    public static void main(String[] args) {

    }

    public int pathSum(TreeNode root, int sum) {
        if (root == null)
            return 0;
        return countPath(root,0,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
    }

    public int countPath(TreeNode root, int sum , int target){
        if (root == null)
            return 0;
        sum += root.val;
        if (sum == target){
            return 1 + countPath(root.left,sum,target) + countPath(root.right,sum,target);
        }
        else
            return countPath(root.left,sum,target) + countPath(root.right,sum,target);
    }
}
